/**
 * 四数之和
 *
 * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
 *
 * 0 <= a, b, c, d < n
 * a、b、c 和 d 互不相同
 * nums[a] + nums[b] + nums[c] + nums[d] == target
 * 你可以按 任意顺序 返回答案 。
 *
 *
 *
 * 示例 1：
 * 输入：nums = [1,0,-1,0,-2,2], target = 0
 * 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
 *
 * 示例 2：
 * 输入：nums = [2,2,2,2,2], target = 8
 * 输出：[[2,2,2,2]]
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 这题和三数之和类似, 不过是这一题是要固定两个数, 然后再选取另外两个数来凑出 target,
 * 当然先来排序和用数组的有序性来优化时间复杂度, 后面判断这个数之前是不是选过, 因为要求的
 * 集合是要求排除相同的 list的
 * 本题与上题不一样的就是要注意数据范围, 这题总和相加可能超出integer 范围, 所以我们要用
 * long类型接收以避免越界
 */

public class Main {
    public List<List<Integer>> fourSum(int[] nums, int target) {

        // 排序数组
        Arrays.sort(nums);

        // 定义返回集合
        List<List<Integer>> ret = new ArrayList<>();

        // 长度
        int n = nums.length;

        // 先固定两个数
        for (int l = n - 1; l > 2; l--) {
            for (int k = l - 1; k > 1; k--) {

                // 后面在这范围之间再选两个数
                int i = 0, j = k - 1;

                // 遍历所有组合
                while (i < j) {

                    // 要定义 long类型,  以免越界
                    long tmp = (long) nums[i] + nums[j] + nums[k] + nums[l];

                    // 注意什么时候排除重复的数
                    // 肯定是在一个数已经计算过了才要排除, 所以在 tmp = target 时排除重复的数
                    if (tmp < target) {
                        i++;
                    } else if (tmp > target) {
                        j--;
                    } else {

                        // 符合要求, 添加进集合
                        ret.add(new ArrayList<>(
                                Arrays.asList(nums[i], nums[j], nums[k], nums[l]))
                        );

                        // 别忘了添加要改变下标
                        i++;
                        j--;

                        // 排除相同的数
                        while (i < j && nums[i] == nums[i - 1]) {
                            i++;
                        }
                        while (i < j && nums[j] == nums[j + 1]) {
                            j--;
                        }
                    }
                }

                // 后面选的两个数要排除, 外面的两个数也是要排除相同的
                while (k > 1 && nums[k] == nums[k - 1]) {
                    k--;
                }
            }
            while (l > 2 && nums[l] == nums[l - 1]) {
                l--;
            }
        }

        // 返回结果
        return ret;
    }

    // 测试越界数据
    public static void main(String[] args) {
        Main test = new Main();
        int[] nums = {1000000000,1000000000,1000000000,1000000000};
        System.out.println(test.fourSum(nums, -294967296));
    }
}